# # -*- coding:utf-8
#
# 5355. T 秒后青蛙的位置 显示英文描述
# 用户通过次数0
# 用户尝试次数0
# 通过次数0
# 提交次数0
# 题目难度Hard
# 给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：
#
# 在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
# 青蛙无法跳回已经访问过的顶点。
# 如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
# 如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。
# 无向树的边用数组 edges 描述，其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边。
#
# 返回青蛙在 t 秒后位于目标顶点 target 上的概率。

from typing import List
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        visited = [0] * (n+1)  #n个点
        graph = [[0 for _ in range(n+1)] for __ in range(n+1)]
        for p1,p2 in edges:
            graph[p1][p2] = 1
            graph[p2][p1] = 1

        # properbility = 1

        step = 0
        lis = [(0,1,1)]  ##step，point,概率
        while lis.__len__()>0:
            step,pidx,prpl = lis.pop(0)
            print("step: ",step," ",pidx)
            visited[pidx] = 1
            if step == t and pidx == target:
                return prpl
            if step+1<= t:
                # zipoints = [p if graph[pidx][p] == 1 and visited[p] == 0 for p in range(n+1)]
                zipoints = []
                for p in range(0,n+1):
                    if graph[pidx][p] == 1 and visited[p] == 0:
                        zipoints.append(p)

                print("子节点",zipoints)

                if zipoints.__len__()>0:
                    newPro = prpl / zipoints.__len__()
                    for newpointid in zipoints:
                        lis.append((step+1,newpointid,newPro))
                else:
                    lis.append((step+1,pidx,prpl))


        return 0

res = Solution().frogPosition(7,
[[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]],
20,
6)
print(res)